
#include <glog/logging.h>
#include <iterator>
#include <numeric>
#include <thread>
#include <vector>

template <typename Iter, typename T>
struct accumulate_block {
    void operator()(Iter first, Iter last, T& res)
    {
        res = std::accumulate(first, last, res);
    }
};

template <typename Iter, typename T>
T parallelism_accumulate(Iter first, Iter last, T init)
{
    size_t length = std::distance(first, last);
    size_t min_num_per_thread = 25;
    size_t max_threads = (length + min_num_per_thread - 1) / min_num_per_thread;
    size_t hardware_threads = std::thread::hardware_concurrency();
    size_t num_threads = std::min(hardware_threads ? hardware_threads : 2, max_threads);
    size_t block_size = length / num_threads;

    std::vector<T> results(num_threads, 0);
    std::vector<std::thread> threads(num_threads - 1);

    Iter block_start = first;
    int i = 0;
    for (auto& t : threads) {
        Iter block_end = block_start;
        std::advance(block_end, block_size);
        t = std::thread(accumulate_block<Iter, T>(), block_start, block_end, std::ref(results[i++]));
        block_start = block_end;
    }
    accumulate_block<Iter, T>()(block_start, last, results[i]);
    for (auto& t : threads) {
        t.join();
    }
    return std::accumulate(results.begin(), results.end(), init);
}

int main(int argc, char* argv[])
{
    google::SetStderrLogging(google::LogSeverity(FLAGS_minloglevel));
    google::InitGoogleLogging(argv[0]);

    auto data = std::vector<float>(1000000, 1.0f);
    LOG(INFO) << parallelism_accumulate<std::vector<float>::iterator, float>(data.begin(), data.end(), 0.0f);
    return 0;
}